/**
 * shell希尔排序算法
 */

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define MAX_ELEMENT 2000
#define MAX_VALUE   1000
#define TRUE 1
#define FALSE 0

void randArray(int a[], int n, int max);
void orderArray(int a[], int n);
void printArray(int a[], int n, int col);
void bubbleSort1(int a[], int n);
void insertSort1(int a[], int n);
void insertSort2(int a[], int n);
void shellSort1(int a[], int n);
void shellSort2(int a[], int n);

int main(void) {
    clock_t time_taken;

    int test_data[MAX_ELEMENT];

    randArray(test_data, MAX_ELEMENT, MAX_VALUE);
    //orderArray(test_data, MAX_ELEMENT);

    printf("Before: \n");
    printArray(test_data, MAX_ELEMENT, 20);
    time_taken = clock();
    bubbleSort1(test_data, MAX_ELEMENT);
    time_taken = clock() - time_taken;
    printf("After: \n");
    printArray(test_data, MAX_ELEMENT, 20);
    printf("time eslapsed: %lu colcks (%lu seconds)\n", time_taken, time_taken / CLOCKS_PER_SEC);

    randArray(test_data, MAX_ELEMENT, MAX_VALUE);
    //orderArray(test_data, MAX_ELEMENT);

    printf("Before: \n");
    printArray(test_data, MAX_ELEMENT, 20);
    time_taken = clock();
    //insertSort2(test_data, MAX_ELEMENT);
    shellSort1(test_data, MAX_ELEMENT);
    time_taken = clock() - time_taken;
    printf("After: \n");
    printArray(test_data, MAX_ELEMENT, 20);
    printf("time eslapsed: %lu colcks (%lu seconds)\n", time_taken, time_taken / CLOCKS_PER_SEC);

    randArray(test_data, MAX_ELEMENT, MAX_VALUE);
    //orderArray(test_data, MAX_ELEMENT);

    printf("Before: \n");
    printArray(test_data, MAX_ELEMENT, 20);
    time_taken = clock();
    shellSort2(test_data, MAX_ELEMENT);
    time_taken = clock() - time_taken;
    printf("After: \n");
    printArray(test_data, MAX_ELEMENT, 20);
    printf("time eslapsed: %lu colcks (%lu seconds)\n", time_taken, time_taken / CLOCKS_PER_SEC);


    return 0;
}

void randArray(int a[], int n, int max) {
    srand(time(0));
    for (int i = 0; i < n; i++)
        a[i] = rand() % max;
}

void orderArray(int a[], int n) {
    for (int i = 0;  i < n; i++)
        a[i] = i;
}

void printArray(int a[], int n, int col) {
    for (int i = 0; i < n; i++) {
        printf("%6d%c", a[i], (i%col == col-1 || i == n-1)? '\n' : ' ');
    }
}

void insertSort1(int a[], int n) {

    for (int i = 1; i < n; i++) {
        int temp = a[i];
        int j = i - 1;
        while (j >=0 && a[j] > temp) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

void insertSort2(int a[], int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i-1; j >=0 && a[j] > a[j+1]; j--) {
            a[j] ^= a[j+1], a[j+1] ^= a[j], a[j] ^= a[j+1];
        }
    }
}

void bubbleSort1(int a[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n-i; j++) {
            if (a[j-1] > a[j]) {
                a[j-1] ^= a[j], a[j] ^= a[j-1], a[j-1] ^= a[j];
            }
        }
    }
}

void shellSort1(int a[], int n) {
    int i, j, k, gap, temp;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = 0; i < gap; i++) {
            for (j = i + gap; j < n; j += gap) {
                temp = a[j];
                k = j - gap;
                while (k >=0 && a[k] > temp) {
                    a[k+gap] = a[k];
                    k -= gap;
                }
                a[k+gap] = temp;
            }
        }
    }
}

void shellSort2(int a[], int n) {
    int gap, i, j;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            for (j = i-gap; j >= 0 && a[j] > a[j+gap]; j -= gap) {
                a[j] ^= a[j+gap], a[j+gap] ^= a[j], a[j] ^= a[j+gap];
            }
        }
    }
}

